#include <stdio.h>
#include <stdlib.h>
#include <LPC21xx.H> 

typedef struct Student{
char initial;
char age;
unsigned short id;
struct Student * next;
} Student;

typedef struct List{
struct Student * head;
}List;
 
/* Your method declarations */

struct Student * student(unsigned int id, unsigned int age, unsigned int initial);
List * list();
//Insert node in the front of the linked list
void insert_front(List *l, Student * s);

//Insert node at the end of the linked list
void insert_back(List *l, Student * s);

//Delete the first (front) node from the linked list
void delete_front(List *l);

//Delete the last node from the linked list
void delete_back(List *l);

//Insert a node after a specific location in the linked list
void insert_middle(List *l, Student * s, int index);

//Delete a specified node (given ID) from the linked list
void delete_data(List *l, unsigned int id);

//Traverse and print the data in the linked list
void display(List *l);

//Search for a given data (ID) whether exist or not in the linked list
unsigned int search(List *l, unsigned int id);

//Reverse the order of the linked list
void reverse(List *l);

//Sort the data (according to ID) in the linked list using an efficient sorting algorithm
void sort(List *l);

//Concatenate the second list at the back of the first then remove the second
void concatenate_lists(List *l1, List *l2);
/* End Methods Declarations */

/* start main */
int main(void) {
	////Your declarations go here
	struct List *l = list();
	struct List *l2 = list();

	PINSEL0 = 0x00050000;           // Enable RxD1 and TxD1                     
	U1DLL = 97;                     // 9600 Baud Rate @ 15MHz VPB Clock         
	U1LCR = 0x03;                   // DLAB = 0    

	insert_front(l, (struct Student *) student(1111,20,'A'));
	insert_front(l, (struct Student *) student(2222,21,'B'));	
	insert_back(l, (struct Student *) student(3333,22,'C'));
	insert_middle(l, (struct Student *) student(4444,23,'D'), 1);
	//insert_middle(l, (struct Student *) student(5555,20,'E'), 2);
	insert_middle(l, (struct Student *) student(5555,20,'E'), 7);
	display(l);
	delete_front(l);
	delete_back(l);
	display(l);
	insert_back(l, (struct Student *) student(7777,20,'F'));
	insert_front(l, (struct Student *) student(6666,21,'B'));
	insert_front(l, (struct Student *) student(8888,22,'C'));
	insert_front(l, (struct Student *) student(9999,23,'D'));
	insert_front(l, (struct Student *) student(1010,20,'E'));
	display(l);
	delete_data(l, 1111);
	delete_data(l, 1212);
	display(l);	
	printf("%d, %d\n", search(l, 2222), search(l, 7777));
	sort(l);
	display(l);
	reverse(l);
	display(l);	
	insert_front(l2, (Student *) student(0001, 10, 'S'));
	concatenate_lists(l, l2);
	display(l);
	display(l2);
	//getchar();
}
/* end main */

/* Start Your method definitions */
// Student constructor
struct Student * student(unsigned int id, unsigned int age, unsigned int initial) {
	struct Student * s = (Student *) malloc(sizeof(Student));
	s->id = (unsigned short)id;
	s->age = (char)age;
	s->initial = (char)initial;
	s->next = NULL;
	return s;
}
// List constructor
List * list() {
	List * l = (List *) malloc(sizeof(List));
	l->head = NULL;
	return l;
}
// Inserts Student s in the front of list l
void insert_front(List *l, Student * s){
	s->next = l->head;
	l->head = s;
}
// Inserts Student s in the back of list l 
void insert_back(List *l, Student * s){
	Student * last = l->head, *pre;
	while(last) { // find last
		pre = last;
		last = last->next;
	}
	if (last != pre) { // check if list is not empty
	   	pre->next = s;	
	} else {
		l->head = s;
   	}
}
// Inserts Student s at index i of list l if the index exist else inserts at the end
void insert_middle(List *l, Student * s, int index){
	struct Student * temp = l->head;
	while(--index != 0 && temp->next != NULL) // find i or end
    	temp = temp->next;
	s->next = temp->next;
	temp->next = s;
}
// deletes the head of the list l
void delete_front(List *l){
	if(l->head){ // not empty
		Student * t = l->head;
		l->head = l->head->next;
		free(t);
	}
}
// deletes the tail of the list l
void delete_back(List *l){
	Student *last = l->head;
	if(last->next) { // if size > 1
		while (last->next->next != NULL) // find before last
			last = last->next;
		free(last->next);
		last->next = NULL;
	} else {
		delete_front(l);
	}
}
// deletes Student with id id if existsfrom list l
void delete_data(List *l, unsigned int id){
 	Student *current = l->head, *befcurrent = current;
	while (current && (int)current->id != id) { // find the Student
      	befcurrent = current;
		current = current->next;
	}
	if (current) { //if found
		if (current == befcurrent) // if head
			l->head = current->next;
		else
			befcurrent->next = current->next;
		free(current);
	}
}
//Traverse and print the data in the linked list
void display(List *l) {
	if (l->head) { // if list exists
		struct Student * c = l->head;
		printf("Start of List:\n");
		while (c) { 
			printf("%c, %d, %d.\n", c->initial,  c->id, c->age);
			c = c->next;
		}
		printf("End of List.\n");
	}
}
//Search for a given data (ID) whether exist or not in the linked list
unsigned int search(List *l, unsigned int id) {
	struct Student *s = l->head;
	for (; s != NULL; s = s->next) {
		if(s->id == id) {
			return 1;
		}
	}
	return 0;
}
// reverse a list l
void reverse(List *l) {
    struct Student *nxtNode, *curNode;
    curNode = l->head;
    l->head = NULL;
    while (curNode != NULL) { // for all
	// reversing pointers
        nxtNode = curNode->next;
        curNode->next = l->head;
        l->head = curNode;
        curNode = nxtNode;
    }
}
//Concatenate the second list at the back of the first then remove the second
void concatenate_lists(List *l1, List *l2) {
	Student *last = l1->head;
	while(last->next != NULL) {
		last = last->next;
	}
	last->next = l2->head;
	l2->head = NULL;
}

//Sort the data (according to ID) in the linked list using an efficient sorting algorithm
void sort(List *l) {
	List *newList = list();
	Student * ptr = 0, *pre = 0;
    Student *n = l->head, *t = 0;
	while(n != NULL) {
		t = n;
		n = n->next;
		t->next = 0;
		//insertSorted(newList, t);
		ptr = newList->head;
		pre = 0;
		while(ptr != NULL && (int) ptr->id < (int) t->id) {
			pre = ptr;
			ptr = ptr->next;
		}
		if (pre) {
			pre->next = t;
			t->next = ptr;	
		} else {
		insert_front(newList, t);
		}
	}
    l->head = newList->head;
	free(newList);
}
/* End Your method definitionss */
